package org.bear.array;

/*
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。

示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

 */
public class MaxSubArray {

    public int maxSubArray2(int[] nums) {
        long minestSum = 0;
        long maxestSub = Long.MIN_VALUE;
        int[] sums = new int[nums.length+1];
        sums[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            sums[i+1] = sums[i] + nums[i];
            long sub = sums[i+1] - minestSum;
            maxestSub = Math.max(maxestSub, sub);
            minestSum = Math.min(minestSum, sums[i+1]);
        }
        return (int)maxestSub;
    }


    int[] nums = null;
    int res = Integer.MIN_VALUE;

//    精妙的 分治法 求解
    public int maxSubArray(int[] nums) {
        this.nums = nums;
        res = nums[0];
        maxSubArray(nums.length-1);
        return res;
    }

    private int maxSubArray(int index){
        if (index == 0){
            return nums[0];
        }
        int sub = maxSubArray(index - 1);
        int curMax = nums[index];
        if (sub > 0){
            curMax += sub;
        }
        res = Math.max(res, curMax);
        return curMax;
    }


    // 动态规划
    public int maxSubArray3(int[] nums){
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = dp[i-1]>0?dp[i-1]+nums[i]:nums[i];
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
